package KI;

import java.util.ArrayList;
import java.util.List;

/**
 * This class finds the way and the destinations for the automatic controlled player
 *
 */
public class KI {

	/**
	 * List of the known Nodes
	 */
	List<Node> bekannt;
	
	/**
	 * List of the unknown Nodes
	 */
	List<Node> untersucht;


	/**
	 * Standard constructor
	 */
	public KI (){
		this.bekannt = null;
		this.untersucht = null;
	}

	/**
	 * Find the best way for the CPU
	 * @param x Start position x
	 * @param y Start position y
	 * @param bombs	The amount of placed bombs
	 * @return The next position
	 */
	public float[] findeWeg(int x, int y, int bombs){

		int zielx = -1;
		int ziely = -1;

		//nach items suchen
		for(int i = 0; i<=4; i++){

			for(int j = 0; j<=4 ; j++){

				if(y+i<game.Multiplayer.map.size-1 && x+j<game.Multiplayer.map.size-1){
					if(game.Multiplayer.map.field[y+i][x+j].type.equals("item")){
						zielx = x+j;
						ziely = y+i;
						break;
					}
				}

				if(y+i<game.Multiplayer.map.size-1 && x-j>=0){
					if(game.Multiplayer.map.field[y+i][x-j].type.equals("item")){
						zielx = x-j;
						ziely = y+i;
						break;
					}
				}

				if(y-i>=0 && x-j>=0){
					if(game.Multiplayer.map.field[y-i][x-j].type.equals("item")){
						zielx = x-j;
						ziely = y-i;
						break;
					}
				}

				if(y-i>=0 && x+j<game.Multiplayer.map.size-1){
					if(game.Multiplayer.map.field[y-i][x+j].type.equals("item")){
						zielx = x+j;
						ziely = y-i;
						break;
					}
				}
			}
		}

		if(zielx >=0 && ziely >=0 && false){
			System.out.println("suche item");

			this.bekannt = new ArrayList<Node>();
			this.untersucht = new ArrayList<Node>();

			this.bekannt.add(new Node(x,y,null,0));

			while(!this.bekannt.isEmpty()){
				if(this.bekannt.get(0).x==zielx && this.bekannt.get(0).y==ziely){
					return this.naechsterSchritt(this.bekannt.get(0), x, y, false);
				}
				else if(this.untersuche(this.bekannt.get(0))){

					int helpx=this.bekannt.get(0).x;
					int helpy=this.bekannt.get(0).y;
					this.untersucht.add(this.bekannt.get(0));
					this.bekannt.remove(0);

					if(helpx+1<game.Multiplayer.map.size-1 && !this.inUntersuchtVorhanden(helpx+1, helpy)){
						if(this.inBekanntVorhanden(helpx+1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx+1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx+1,helpy,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}

					if(helpy+1<game.Multiplayer.map.size-1  && !this.inUntersuchtVorhanden(helpx, helpy+1)){
						if(this.inBekanntVorhanden(helpx, helpy+1, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx, helpy+1, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx,helpy+1,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}

					if(helpx-1>=0 && !this.inUntersuchtVorhanden(helpx-1, helpy+1)){
						if(this.inBekanntVorhanden(helpx-1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx-1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx-1,helpy,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}

					if(helpy-1>=0  && !this.inUntersuchtVorhanden(helpx, helpy-1)){
						if(this.inBekanntVorhanden(helpx, helpy-1, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx, helpy-1, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx,helpy-1,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}
				}
				else{
					this.untersucht.add(this.bekannt.get(0));
					this.bekannt.remove(0);
				}

			}

		}
		else if(bombs >0){
			System.out.println("suche bombe");

			this.bekannt = new ArrayList<Node>();
			this.untersucht = new ArrayList<Node>();

			this.bekannt.add(new Node(x,y,null,0));

			while(!this.bekannt.isEmpty()){

				if(this.untersucheBombe(this.bekannt.get(0))){
					System.out.println("und findet");
					return this.naechsterSchritt(this.bekannt.get(0), x, y, true);
				}
				else if(this.untersuche(this.bekannt.get(0))){

					int helpx=this.bekannt.get(0).x;
					int helpy=this.bekannt.get(0).y;
					this.untersucht.add(this.bekannt.get(0));
					this.bekannt.remove(0);

					if(helpx+1<game.Multiplayer.map.size-1 && !this.inUntersuchtVorhanden(helpx+1, helpy)){
						if(this.inBekanntVorhanden(helpx+1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx+1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx+1,helpy,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}

					if(helpy+1<game.Multiplayer.map.size-1  && !this.inUntersuchtVorhanden(helpx, helpy+1)){
						if(this.inBekanntVorhanden(helpx, helpy+1, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx, helpy+1, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx,helpy+1,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}

					if(helpx-1>=0 && !this.inUntersuchtVorhanden(helpx-1, helpy+1)){
						if(this.inBekanntVorhanden(helpx-1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx-1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx-1,helpy,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}

					if(helpy-1>=0  && !this.inUntersuchtVorhanden(helpx, helpy-1)){
						if(this.inBekanntVorhanden(helpx, helpy-1, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx, helpy-1, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx,helpy-1,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}
				}
				else{
					this.untersucht.add(this.bekannt.get(0));
					this.bekannt.remove(0);
				}
			}
		}
		else{
			System.out.println("suche sicher");
			
			this.bekannt = new ArrayList<Node>();
			this.untersucht = new ArrayList<Node>();

			this.bekannt.add(new Node(x,y,null,0));

			while(!this.bekannt.isEmpty()){

				if(this.untersucheSicher(this.bekannt.get(0))){
					return this.naechsterSchritt(this.bekannt.get(0), x, y, false);
				}
				else if(this.untersuche(this.bekannt.get(0))){

					int helpx=this.bekannt.get(0).x;
					int helpy=this.bekannt.get(0).y;
					this.untersucht.add(this.bekannt.get(0));
					this.bekannt.remove(0);

					if(helpx+1<game.Multiplayer.map.size-1 && !this.inUntersuchtVorhanden(helpx+1, helpy)){
						if(this.inBekanntVorhanden(helpx+1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx+1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx+1,helpy,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}

					if(helpy+1<game.Multiplayer.map.size-1  && !this.inUntersuchtVorhanden(helpx, helpy+1)){
						if(this.inBekanntVorhanden(helpx, helpy+1, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx, helpy+1, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx,helpy+1,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}

					if(helpx-1>=0 && !this.inUntersuchtVorhanden(helpx-1, helpy+1)){
						if(this.inBekanntVorhanden(helpx-1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx-1, helpy, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx-1,helpy,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}

					if(helpy-1>=0  && !this.inUntersuchtVorhanden(helpx, helpy-1)){
						if(this.inBekanntVorhanden(helpx, helpy-1, this.untersucht.get(this.untersucht.size()-1).cost+1)>=0){
							this.bekannt.get(this.inBekanntVorhanden(helpx, helpy-1, this.untersucht.get(this.untersucht.size()-1).cost+1)).cost
							=this.untersucht.get(this.untersucht.size()-1).cost+1;		
						}
						else{
							this.bekannt.add(new Node(helpx,helpy-1,this.untersucht.get(this.untersucht.size()-1),this.untersucht.get(this.untersucht.size()-1).cost+1));
						}
					}
				}
				else{
					this.untersucht.add(this.bekannt.get(0));
					this.bekannt.remove(0);
				}
			}
		}
		return new float[]{x,y,0};
	}

	/**
	 * Decides if next field can be used by A* algorithm
	 * @param n The tested node
	 * @return Returns true, if the node can be used
	 */
	private boolean untersuche(Node n){

		if(game.Multiplayer.map.field[n.y][n.x].destroy==false){
			return false;
		}
		else if(game.Multiplayer.map.field[n.y][n.x].type.equals("fire")){
			return false;
		}
		else if(game.Multiplayer.map.field[n.y][n.x].type.equals("bomb")){
			return false;
		}
		else{
			return true;
		}
	}

	/**
	 * Decides if field can be used to set a Bomb
	 * @param n The tested node
	 * @return Returns true, if a bomb can be set here
	 */
	private boolean untersucheBombe(Node n){

		if(!game.Multiplayer.map.field[n.y][n.x].type.equals("space")){
			return false;
		}
		else{
			if(n.x+1<game.Multiplayer.map.size){
				if(game.Multiplayer.map.field[n.y][n.x+1].type.equals("block") && game.Multiplayer.map.field[n.y][n.x+1].destroy){
					return true;
				}
			}

			if(n.y+1<game.Multiplayer.map.size){
				if(game.Multiplayer.map.field[n.y+1][n.x].type.equals("block") && game.Multiplayer.map.field[n.y+1][n.x].destroy){
					return true;
				}
			}

			if(n.x-1>=0){
				if(game.Multiplayer.map.field[n.y][n.x-1].type.equals("block") && game.Multiplayer.map.field[n.y][n.x-1].destroy){
					return true;
				}
			}

			if(n.y-1>=0){
				if(game.Multiplayer.map.field[n.y-1][n.x].type.equals("block") && game.Multiplayer.map.field[n.y-1][n.x].destroy){
					return true;
				}
			}
			return false;
		}
	}
	
	/**
	 * Decides if this field is safe
	 * @param n The tested node
	 * @return Returns true, if field is safe
	 */
	private boolean untersucheSicher(Node n){
		
		if(!game.Multiplayer.map.field[n.y][n.x].type.equals("space")){
			return false;
		}
		else{
			for(int i=0; i<game.Multiplayer.map.size-1; i++){
				if(n.x+i<game.Multiplayer.map.size-1){
					if(game.Multiplayer.map.field[n.y][n.x+i].type.equals("block")){
						break;
					}
					else if(game.Multiplayer.map.field[n.y][(n.x+i)].type.equals("bomb")){
						return false;
					}
				}
				else{
					break;
				}
			}
			
			for(int i=0; i<game.Multiplayer.map.size-1; i++){
				if(n.y+i<game.Multiplayer.map.size-1){
					if(game.Multiplayer.map.field[n.y+i][n.x].type.equals("block")){
						break;
					}
					else if(game.Multiplayer.map.field[n.y+i][n.x].type.equals("bomb")){
						return false;
					}
				}
				else{
					break;
				}
			}
			
			for(int i=0; i<game.Multiplayer.map.size-1; i++){
				if(n.x-i>=0){
					if(game.Multiplayer.map.field[n.y][n.x-i].type.equals("block")){
						break;
					}
					else if(game.Multiplayer.map.field[n.y][n.x-i].type.equals("bomb")){
						return false;
					}
				}
				else{
					break;
				}
			}
			
			for(int i=0; i<game.Multiplayer.map.size-1; i++){
				if(n.y-i>=0){
					if(game.Multiplayer.map.field[n.y-i][n.x].type.equals("block")){
						break;
					}
					else if(game.Multiplayer.map.field[n.y-i][n.x].type.equals("bomb")){
						return false;
					}
				}
				else{
					break;
				}
			}
			return true;
			
		}
		
	}

	/**
	 * Tests if node is already known
	 * @param x X position
	 * @param y Y position
	 * @param cost Costs on the way to this node
	 * @return The index of this node, if already known
	 */
	private int inBekanntVorhanden(int x, int y, int cost){
		for(int i=0; i<this.bekannt.size();i++){
			if(this.bekannt.get(i).x==x && this.bekannt.get(i).y==y && this.bekannt.get(i).cost > cost){
				return i;
			}
		}
		return -1;
	}

	/**
	 * Tests if node is already reviewed
	 * @param x X position
	 * @param y Y position
	 * @return Returns true, if node is already reviewed
	 */
	private boolean inUntersuchtVorhanden(int x, int y){
		for(int i=0; i<this.untersucht.size();i++){
			if(this.untersucht.get(i).x==x && this.untersucht.get(i).y==y){
				return true;
			}
		}
		return false;
	}

	/**
	 * Gives the next Step of the whole path
	 * @param node This is the destination
	 * @param x X position
	 * @param y Y position
	 * @param bomb Is true, if Bomber should set a bomb
	 * @return Returns the next Position
	 */
	private float[] naechsterSchritt(Node node, int x, int y, boolean bomb){
		Node n = node;
		int count=0;
		while(n.pre!=null){
			if(n.pre.x==x && n.pre.y==y){
				if(bomb && count==0){
					return new float[]{n.x, n.y, 1};
				}
				else{
					return new float[]{n.x, n.y, 0};
				}
			}
			else{
				n=n.pre;
			}
			count ++;
		}
		return new float[]{x, y,0};
	}
}
